# 有序链表转换二叉搜索树


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 将链表转为数组，需要额外的存储空间
# class Solution(object):
#     def sortedListToBST(self, head):
#         """
#         :type head: Optional[ListNode]
#         :rtype: Optional[TreeNode]
#         """
#         nums = []
#         while (head):
#             nums.append(head.val)
#             head = head.next
#         return self.build(nums, 0, len(nums)-1)

#     def build(self, nums, left, right):
#         if left > right:
#             return None

#         mid = (right + left) // 2

#         root = TreeNode(nums[mid])
#         root.left = self.build(nums, left, mid-1)
#         root.right = self.build(nums, mid+1, right)

#         return root


## 使用快慢指针找链表的中间数
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[TreeNode]
        """
        if not head:
            return None
        return self.build(head, None)

    def build(self, head, tail):
        """
        head,tail:TreeNode
        """
        if (head == tail):
            return None
        # 定义快慢指针
        fast = head
        slow = head
        while fast != tail and fast.next != tail:
            fast = fast.next.next
            slow = slow.next
        root = TreeNode(slow.val)
        root.left = self.build(head, slow)
        root.right = self.build(slow.next, tail)
        return root
